#include "myGraph.h"
#include <iostream>
#include <sstream>
#include <string>
#include <queue>

using namespace std;

EdgeNode::EdgeNode()
{
    dest=0;
    link=nullptr;

}

EdgeNode::EdgeNode(int d, EdgeNode* l)
{
    dest=d;
    link=l;
}

EdgeNode::~EdgeNode()
{

}

int EdgeNode::getDest()//获取目标节点
{
    return dest;

}

EdgeNode* EdgeNode::getNext()
{
    return link;
}

void EdgeNode::setDest(int d)
{
    dest=d;
}

void EdgeNode::setNext(EdgeNode* l)
{
    link=l;
}


VertexNode::VertexNode()
{
    data=' ';
    firstEdge=nullptr;
}

VertexNode::VertexNode(char d, EdgeNode* f)
{
    data=d;
    firstEdge=f;
}

VertexNode::~VertexNode()
{
    EdgeNode* current = firstEdge;
    while (current) 
    {
        EdgeNode* temp = current;
        current = current->getNext();
        delete temp; // 释放每个边节点的内存
    }
}

char VertexNode::getData()
{
    return data;
}

EdgeNode* VertexNode::getFirstEdge()
{
    return firstEdge;
}

void VertexNode::setData(char d)
{
    data=d;
}

void VertexNode::setFirstEdge(EdgeNode* f)
{
    firstEdge=f;
}


MyGraph::MyGraph()
{
    nodeNum=0;
    edgeNum=0;
    VexList=nullptr;
}

MyGraph::MyGraph(int n, int e, char* nodeList, int* edgeStartList, int* edgeEndList)
{
    nodeNum=n;
    edgeNum=e;
    VexList=new VertexNode[nodeNum];
    
    for (int i = 0; i < nodeNum; ++i) 
    {
        VexList[i].setData(nodeList[i]);
        VexList[i].setFirstEdge(nullptr);
    }
    // 初始化顶点

    for (int i = 0; i < edgeNum; ++i)
    {
        int start = edgeStartList[i];
        int end = edgeEndList[i];
        VexList[start].setFirstEdge(new EdgeNode(end, VexList[start].getFirstEdge())); 
        VexList[end].setFirstEdge(new EdgeNode(start, VexList[end].getFirstEdge())); // 反向边
    }
    //初始化边
}

MyGraph::~MyGraph()
{
    delete[] VexList; 
}

int MyGraph::getNodeNum()
{
    return nodeNum;
}

int MyGraph::getEdgeNum()
{
    return edgeNum;
}

string MyGraph::printGraph()
{
    stringstream ss;
    for (int i = 0; i < nodeNum; i++) 
    {
        ss << VexList[i].getData() << ":"; // 打印起点节点数据
        EdgeNode* edge = VexList[i].getFirstEdge();
        while (edge != nullptr) 
        {
            ss << " " << VexList[edge->getDest()].getData(); // 打印相邻节点
            edge = edge->getNext();
        }
        ss << "\n"; 
    }
    string result = ss.str();
    result.erase(result.end()-1); // 移除最后的换行符
    return result;
}

int MyGraph::getFirstNeighbor(int v, int* visited)
{
    (void)visited; 
    EdgeNode* edge = VexList[v].getFirstEdge();
    return edge ? edge->getDest() : -1; // 返回第一个邻居
}

int MyGraph::getNextNeighbor(int v, int w, int* visited)
{
    (void)visited;
    EdgeNode* edge = VexList[v].getFirstEdge();
    while (edge) 
    {
        if (edge->getDest() == w) 
        { // 找到目标邻居
            edge = edge->getNext();
            return edge ? edge->getDest() : -1; // 返回下一个邻居
        }
        edge = edge->getNext();
    }
    return -1; 
}

void MyGraph::DFS(int v, int* visited, string& result)
{
    visited[v] = 1; // 标记为已访问
    result += VexList[v].getData();
    result += ' ';
    
    // 获取邻居并递归访问
    for (int w = getFirstNeighbor(v, visited); w != -1; w = getNextNeighbor(v, w, visited)) 
    {
        if (!visited[w]) //未被访问过
        {
            DFS(w, visited, result); // 递归调用
        }
    }
}

string MyGraph::graph_DFS_Traverse()
{
    string result;
    int* visited = new int[nodeNum] {}; // 初始化访问数组
    for (int i = 0; i < nodeNum; ++i) 
    {
        if (!visited[i]) 
        {
            DFS(i, visited, result); // 这里要考虑图不是连通图的情况，进行多次访问
        }
    }
    delete[] visited; 
    return result;
}

void MyGraph::BFS(int v, int* visited, string& result)
{
    queue<int> q;
    visited[v] = 1; // 标记为已访问
    q.push(v); // 入队
    
    while (!q.empty()) 
    {
        int current = q.front();
        q.pop();
        result += VexList[current].getData();
        result += ' ';
        
        // 获取邻居并入队
        for (int w = getFirstNeighbor(current, visited); w != -1; w = getNextNeighbor(current, w, visited)) 
        {
            if (!visited[w]) 
            {
                visited[w] = 1; // 标记为已访问
                q.push(w); // 入队
            }
        }
    }
}

string MyGraph::graph_BFS_Traverse()
{
    string result;
    int* visited = new int[nodeNum] {}; // 初始化访问数组
    for (int i = 0; i < nodeNum; ++i) 
    {
        if (!visited[i]) 
        {
            BFS(i, visited, result); // 这里要考虑图不是连通图的情况，进行多次访问
        }
    }
    delete[] visited; 
    return result; 
}